package leetcode.biweekly.week82;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

import leetcode.helper.H;

//Solution2Test
public class Solution2 {
	// Solution2Test

	public int latestTimeCatchTheBus(int[] buses, int[] passengers, int capacity) {
		Arrays.sort(buses);
		Arrays.sort(passengers);
		int ans = 0, p = 0;
		Set<Integer> set = new HashSet<>();
		int cnt = 0;
		for (int i = 0; i < buses.length; i++) {
			int bus = buses[i];
			cnt = capacity;
			while (p < passengers.length && passengers[p] <= bus && cnt > 0) {
				set.add(passengers[p]);
				p++;
				cnt--;
			}
		}
		int start = cnt > 0 ? buses[buses.length - 1] : passengers[p - 1] - 1;
		for (int i = start; i > 0; i--) {
			if (!set.contains(i)) {
				return i;
			}
		}
		return ans;
	}

}
